package class08;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

/**
 * 给定一棵二叉树的头节点head, 和另外两个节点a和b
 * 返回a和b的最低公共祖先(a和b首次交会的节点)
 */
public class Code07_lowestAncestor {

	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	/**
	 * 暴力法:
	 * 先把节点 o1(a), 向上找整棵树的head节点, 并且把沿途的所有节点加入hashset中
	 * 再对 o2(b), 向上找整棵树的head节点, 并沿途判断父节点是否在 o1的哈希表(hashset)中
	 * 第一次发现存在的节点就是最低公共祖先
	 *
	 * @param head 树的head节点
	 * @param o1 节点1
	 * @param o2 节点2
	 * @return
	 */
	public static Node lowestAncestor1(Node head, Node o1, Node o2) {
		if (head == null) {
			return null;
		}
		// key的父节点是value
		HashMap<Node, Node> parentMap = new HashMap<>();
		parentMap.put(head, null);
		//生成整棵树的映射关系: k=当前节点, v=父节点
		fillParentMap(head, parentMap);
		//生成o1向上找父的set(二叉树默认不会有指向父的指针,所以需要查map)
		HashSet<Node> o1Set = new HashSet<>();
		Node cur = o1;
		o1Set.add(cur);
		while (parentMap.get(cur) != null) {
			cur = parentMap.get(cur);
			o1Set.add(cur);
		}
		//节点o2去查o1的set
		cur = o2;
		while (!o1Set.contains(cur)) {
			cur = parentMap.get(cur);
		}
		return cur;
	}

	public static void fillParentMap(Node head, HashMap<Node, Node> parentMap) {
		if (head.left != null) {
			parentMap.put(head.left, head);
			fillParentMap(head.left, parentMap);
		}
		if (head.right != null) {
			parentMap.put(head.right, head);
			fillParentMap(head.right, parentMap);
		}
	}

	//根据x(子树头节点, 中间节点, 左中右)进行分类讨论
	//1. o1,o2 没有一个在x上为头节点的子树上
	//2. o1,o2 只有一个在x上为头节点的子树上
	//3. o1,o2 都在x上为头节点的子树上
	//  3.1 左右各一个
	//  3.2 左边是 o1,o2
	//  3.3 右边是 o1,o2
	//  3.4 x本身就是是 o1或o2
	public static Node lowestAncestor2(Node head, Node o1, Node o2) {
		return process(head, o1, o2).ans;
	}

	// 任何子树，
	public static class Info {
		//交汇点,不是交汇点返回null
		public Node ans;
		//子树是否包含o1节点
		public boolean findO1;
		//子树是否包含o2节点
		public boolean findO2;

		public Info(Node a, boolean f1, boolean f2) {
			ans = a;
			findO1 = f1;
			findO2 = f2;
		}
	}

	public static Info process(Node X, Node o1, Node o2) {
		if (X == null) {
			return new Info(null, false, false);
		}
		//向子树索要信息
		Info leftInfo = process(X.left, o1, o2);
		Info rightInfo = process(X.right, o1, o2);
		//根据索要的子树信息判断是否找到o1和o2
		boolean findO1 = X == o1 || leftInfo.findO1 || rightInfo.findO1;
		boolean findO2 = X == o2 || leftInfo.findO2 || rightInfo.findO2;
		// 	O1和O2最初的交汇点在哪？
		// 1) 在左树上已经提前交汇了
		// 2) 在右树上已经提前交汇了
		// 3) 没有在左树或者右树上提前交汇，O1  O2 全了
		Node ans = null;
		//左右树已经找到答案了
		if (leftInfo.ans != null) {
			ans = leftInfo.ans;
		}
		if (rightInfo.ans != null) {
			ans = rightInfo.ans;
		}
		//未找到答案,但是已经找到o1和o2,那么当前x就是最低公共祖先
		if (ans == null) {
			if (findO1 && findO2) {
				ans = X;
			}
		}
		//递归返回需要收集的信息
		return new Info(ans, findO1, findO2);
	}

	// for test
	public static Node generateRandomBST(int maxLevel, int maxValue) {
		return generate(1, maxLevel, maxValue);
	}

	// for test
	public static Node generate(int level, int maxLevel, int maxValue) {
		if (level > maxLevel || Math.random() < 0.5) {
			return null;
		}
		Node head = new Node((int) (Math.random() * maxValue));
		head.left = generate(level + 1, maxLevel, maxValue);
		head.right = generate(level + 1, maxLevel, maxValue);
		return head;
	}

	// for test
	public static Node pickRandomOne(Node head) {
		if (head == null) {
			return null;
		}
		ArrayList<Node> arr = new ArrayList<>();
		fillPrelist(head, arr);
		int randomIndex = (int) (Math.random() * arr.size());
		return arr.get(randomIndex);
	}

	// for test
	public static void fillPrelist(Node head, ArrayList<Node> arr) {
		if (head == null) {
			return;
		}
		arr.add(head);
		fillPrelist(head.left, arr);
		fillPrelist(head.right, arr);
	}

	public static void main(String[] args) {
		int maxLevel = 4;
		int maxValue = 100;
		int testTimes = 1000000;
		for (int i = 0; i < testTimes; i++) {
			Node head = generateRandomBST(maxLevel, maxValue);
			Node o1 = pickRandomOne(head);
			Node o2 = pickRandomOne(head);
			if (lowestAncestor1(head, o1, o2) != lowestAncestor2(head, o1, o2)) {
				System.out.println("Oops!");
			}
		}
		System.out.println("finish!");
	}

}
